package lfu;

import java.util.*;

/**
 * @Author Chill_Lyn
 * @Date 2021/3/23 16:11
 */
public class LFU<K,V> {

    /**
     *  总容量
     */
    private int capacity;

    /**
     * 所有的node节点
     */
    private Map<K, Node<K,V>> caches;
    /**
     * 构造方法
     * @param size
     */
    public LFU(int size) {
        this.capacity = size;
        caches = new LinkedHashMap<K,Node<K,V>>(size);
    }

    /**
     * 添加元素
     * @param key
     * @param value
     */
    public void put(K key, V value) {
        Node<K,V> node = caches.get(key);
        //如果新元素
        if (Objects.isNull(node)) {
            //如果超过元素容纳量
            if (caches.size() >= capacity) {
                //移除count计数最小的那个key
                K leastKey = getLeastCountKey();
                caches.remove(leastKey);
            }
            //创建新节点
            node = new Node<K,V>(key,value,System.nanoTime(),1);
            caches.put(key, node);
        }else {
            //已经存在的元素覆盖旧值
            node.value = value;
            node.setCount(node.getCount()+1);
            node.setTime(System.nanoTime());
        }
        sort();
    }

    /**
     * 获取统计数或者时间比较最小的节点
     * @return
     */
    private K getLeastCountKey() {
        Collection<Node<K,V>> values = caches.values();
        Node<K,V> min = Collections.min(values);
        return (K) min.getKey();
    }

    /**
     * 排序
     */
    private void sort() {

        List<Map.Entry<K, Node<K,V>>> list = new ArrayList<>(caches.entrySet());
        list.sort((o1, o2) -> o2.getValue().compareTo(o1.getValue()));
        caches.clear();
        for (Map.Entry<K, Node<K,V>> kNodeEntry : list) {
            caches.put(kNodeEntry.getKey(),kNodeEntry.getValue());
        }
    }

    /**
     * 获取元素
     * @param key
     * @return
     */
    public V get(K key){
        Node<K,V> node = caches.get(key);
        if (node!=null){
            node.setCount(node.getCount()+1);
            node.setTime(System.nanoTime());
            sort();
            return (V)node.value;
        }
        return null;
    }
}
